CUE’s merge operation is a commutative partial monoid.
We will show that merge operation is associative, has an identity element, and is commutative.
Let each JSON object be a set of key-value pairs where represents keys and values.
Note that CUE’s merge operation can fail under certain conditions, e.g. duplicate keys or unsatisfied constraints. Hence we call the merge operation partial. For the rest of the proof, assume our JSON objects have no duplicate keys nor unsatisfiable constraints.
Let’s demonstrate associativity. Consider three arbitrary JSON objects.
Then to prove associativity, we will show the following.
For every merge operation, we simply reduce to the union of all key-value pairs in the merge. We’ll compute the left of the above equation by first reducing .
We then perform a similar reduction for the right side.
Thus merge is associative.
Our identity element is the empty JSON object . Note the following for any JSON object .
Like our associativity demonstration, this follows from simple reduction.
Given arbitrary JSON objects , we will show that .
Thus merge is commutative.
Since our partial operation merge is commutative, associative, and has an identity element, then it is a commutative partial monoid.